#include <iostream>

using namespace std;

// .h header file 头文件

/*
连续的数据结构：vector<T>
  问题：在中间插入内容的时候，效率不好

不连续的数据结构
*/

// 先有一个自定义类型，表示节点
class Node {
public:
  // 节点里保存的值是什么？
  int value;

  // 节点的下一个节点在哪里？
  Node *next;

  // 定义构造函数
  Node(int v, Node *pn): value(v), next(pn) {
    cout << "A node with value " << v << "was created." << endl;
  }
};

class LinkedList {
public:
  // 头是什么？
  Node *head;

  // 创建一个以 h 作为头部的链表
  // 构造函数
  LinkedList() : head(nullptr) {}
  // 析构函数 - 在对象被销毁的时候自动调用
  ~LinkedList() {
    // 逐一归还我们申请过的节点
    // 我们应该按照什么顺序来归还？
    // delete 要删除的内容的位置;
    // 保存 head->next
    // delete head
    // 更新 head 指向下一个位置
    // 什么情况下，链表算是删干净了？ <-> head == nullptr
    Node *curr = head; // curr - 当前要删除的节点

    while (curr != nullptr) {
      cout << "节点值为: " << curr->value << "的 Node 被回收了." << endl;

      Node *next = curr->next;
      delete curr;

      head = next;
      curr = next;
    }

    cout << "LinkedList is deallocated." << endl;
  }


  // 如何能在链表的末尾添加 element？
  void push_back(int v) {
    // 1. 用 n 作为 value 创建一个 Node
    Node *pn = new Node {v, nullptr};

    // 2. 把这个创建出来的 Node 挂到链表上
    push_back(pn);
  }

  void push_back(Node *element) {
    // 从 head 开始向后遍历，直到链表的最后一个元素
    // 让它的 next 指向 element。
    if (head == nullptr) {
      head = element;
      return;
    }

    Node *pos = head;

    // 对于空链表来说 pos 也是 nullptr
    while (pos->next != nullptr) {
      pos = pos->next;
    }

    pos->next = element;
  }

  void print_list() {
    if (head == nullptr) {
      cout << "An empty list." << endl;
      return;
    }

    Node *pos = head;

    while (pos != nullptr) {
      cout << pos->value << " ";
      pos = pos->next;
    }
    cout << endl;
  }

  bool find(int v) {
    return false;
  }



  // insert 在指定的节点后面添加一个新的节点
  // 在 pos 后面，插入一个值为 v 的节点。
  void insert(Node *pos, int v) {
    // 判断插入的位置本身是不是空的
    if (pos == nullptr) {
      // 设置 head
      head = new Node(v, nullptr);
    }
    else {
      Node *node = new Node(v, pos->next);
      pos->next = node;
    }
  }

  // 删除链表上第一个值为 v 的节点。
  void remove(int v) {
    
  }
};
